package leetcode_900;

import java.util.LinkedList;
import java.util.Queue;

/**
 *@author 周杨
 *ShortestPathVisitingAllNodes_847_ 给定一个无向连接图 问最短多少次数能走遍每个节点 每个节点都可以重复走 每条边都可以重复遍历
 *describe:用bit记录遍历状态 now记录当前的节点 来记录遍历的状态  用BFS AC 70% 非常好的题目
 *2018年11月3日 上午10:43:07
 */
public class ShortestPathVisitingAllNodes_847_ {
	
	public int shortestPathLength(int[][] graph) {
		int n=graph.length;
		int target=(1<<n)-1;//表示最终状态
		Queue<int[]> queue=new LinkedList<int[]>();
		boolean visited[][]=new boolean[n][1<<n];
		for(int i=0;i<n;++i) {
			queue.offer(new int[] {i,1<<i});//初始状态就只有i被访问过
		}
		int res=0;
		while(!queue.isEmpty()) {
			int size=queue.size();
			while(size>0) {
				--size;
				int now[]=queue.poll();
				if(now[1]==target)
					return res;//如果状态达到了最终状态
				if(visited[now[0]][now[1]])
					continue;//此状态被访问过
				visited[now[0]][now[1]]=true;
				for(int next:graph[now[0]])
					queue.offer(new int[] {next,now[1]|(1<<next)});//将状态置为走过
			}
			++res;
		}
		return res;
    }
}
